![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
We have spent over one thousand man-hours cryptanalyzing Twofish. A summary of our successful attacks is as follows:
The fact that Twofish seems to resist related-key attacks well is arguably the most interesting result, because related-key attacks give the attacker the most control over the cipher's inputs. Conventional cryptanalysis allows an attacker to control both the plaintext and ciphertext inputs into the cipher. Related-key cryptanalysis gives the attacker an additional way into a cipher: the key schedule. A cipher that is resistant to attacks with related keys is necessarily resistant to simpler techniques that only involve the plaintext and ciphertext.1
1We have discussed the relevance of related-key attacks to practical implementations of a block cipher in [KSW96, KSW97]. Most importantly, related-key attacks affect a cipher's ability to be used as a one-way hash function.
Based on our analysis, we conjecture that there exists no more efficient attack on Twofish than brute force. That is, we conjecture that the most efficient attack against Twofish with a 128-bit key has a complexity of 2128; the most efficient attack against Twofish with a 192-bit key has a complexity of 2192; and the most efficient attack against Twofish with a 256-bit key has a complexity of 2256.
Cipher variant | Rounds | Work | Memory |
---|
256-bit key, Fixed S, no whitening, no rotations | 11 | 2232 | 2225 |
256-bit key, Fixed S, no whitening | 10 | 2232 | 2225 |
256-bit key, Fixed S | 6 | 2232 | 2225 |
256-bit key, Full Twofish | 4 | 2232 | 2225 |
Table 9.1. Attack Results for Our Meet-in-the-Middle Attack
Table 9.1 summarizes our attack results. One notable feature of this attack is that it demonstrates the impact of adding the pre- and post-whitening and the key-dependent S-boxes. Without these two features, we would have an extremely simple attack on 10 out of the 16 rounds of our cipherenough to raise questions about its ultimate security. With these two features, however, the attack extends to only four rounds. Resistance to meet-in-the-middle attacks comes from quickly getting every bit of the key involved in every bit of the block being encrypted.
In a meet-in-the-middle attack, we try to derive some intermediate state inside the cipher, using only part of the key material from both the plaintext and the ciphertext. For each possible value that the part of the key that we guessed can take, we derive that intermediate value from the plaintext and also from the ciphertext. We get two huge lists of possible intermediate values. We then sort the two lists, and check them for matching values. A matching value of more bits than we would expect to occur randomly indicates that our guesses were correct. This kind of attack is important to consider because the AES candidates are using large keys, which imply a very high security level. A user expecting 256 bits worth of security should be concerned by attacks that involve guessing 200 bits of key in each direction. Also, it is easy for cipher designers used to thinking in terms of 64-bit blocks and 128-bit keys to design ciphers that do not get all 256 bits of key involved in the encryption process quickly enough.
In this Twofish variant, all key material is in the round subkeys. We acquire about 256 plaintext/ciphertext pairs from this Twofish variant with ten rounds.
We label the four words of the data during the encryption as A, B, C, and D. From the plaintext side, we guess the round subkeys for the first three rounds, for a total of 192 bits. We also guess one subkey (used to determine the value XORed into A) in the fourth round. We thus know the value of the low-order bit of D after the fifth round, because (1) we knew the value of D after the third round, (2) we know the value of A going into the fifth round, and (3) we know that the low-order bit of the value XORed into D is dependent only on A and one bit of the fifth round's subkey. For each of the 2225 possibilities for these key values, we compute this bit for all 256 plaintexts we have. We store these in a list, and sort them.
From the ciphertext side, we guess the round keys for the tenth, ninth, and eighth rounds, and we guess the subkey from the seventh round that affects the value XORed into D. We use this to derive the high-order bit from D going into the seventh round, which was rotated from its position as the low-order bit of D after the fifth round. Again, for all 2224 possible key values guessed, we compute this bit for each of the 256 ciphertexts we have. Again, we sort this list.
We now merge the two sorted lists, and thus search for matches. This ought to take on the order of 2232 work total. Thus, we use 2225 blocks of memory, and about 2232 work to break ten rounds of Twofish with fixed S-boxes and no whitening.
Note that without the one-bit rotations in the cipher, we would have needed to know only the low-order bit of the F-function output in the seventh round. This would actually allow us to attack one more round. This is evidence that the one-bit rotations do, in fact, provide some resistance against real attacks.
With the whitening added, the attack becomes much harder. From the plain-text side, we must guess all four pre-whitening subkeys, allowing us to get our known low-order bit only into the output of the third round. Similarly, from the ciphertext side, we must guess all four post-whitening subkeys and the last rounds subkeys, and one subkey word from the next-to-last round. We can thus attack only six rounds in this case.
Attacking the full Twofish is still harder. From the plaintext side, we must guess the 128 bits of S, the round subkey that determines the value that is XORed into C in the first round, and the pre-whitening subkey for C. This allows us to predict the low-order bit of B after the second round XORed with an unknown constant (i.e., we predict that this bit will take on a sequence of values or the negation of that sequence). A similar approach is used from the ciphertext side, allowing only four rounds to be attacked.
Key Length | Variant | Rounds | Chosen Texts | Work |
---|
128 | No whitening, fixed S | 7 | 241 | 2126 |
192 | No whitening, fixed S | 8 | 241 | 2190 |
256 | No whitening, fixed S | 9 | 241 | 2254 |
128 | No whitening, no one-bit rotates | 6 | 241 | 2126 |
192 | No whitening, no one-bit rotates | 6 | 241 | 2158 |
256 | No whitening, no one-bit rotates | 7 | 241 | 2254 |
256 | Normal Twofish | 5 | 241 | 2232 |
Table 9.2. Attack Results for Our Differential Attack
Table 9.2 summarizes our attack results against several variants of Twofish.
The attack uses two different differential properties of the F function:
Our attack works by first trying to force the second event described above to occur in the second round, in a batch of several pairs of plaintexts. If it occurs, then the first event described above occurs in the next round with probability one, resulting in a single bit whose difference is known in the output of the fourth round. This allows an attack on reduced-round Twofish.
The attack requires that we get a specific, predictable difference sequence. We choose
r | ΔRr,0 | ΔRr,1 | ΔRr,2 | ΔRr,3 | |
---|---|---|---|---|---|
0 | 0 | 0 | a′ | b′ | |
1 | a | b | 0 | 0 | |
2 | 0 | ? | a | b | |
3 | ? | (?,1) | 0 | ? | |
4 | ? | ? | ? | (?,1) | |
5 | ? | ? | ? | ? |
where the table gives the difference patterns for the round values for each of the 5 rounds, and where a′ = ROL(a, 1), b′ = ROR(b, 1), and (?, 1) represents a 32-bit difference of which one bit is known. To recognize right pairs, we shall (roughly speaking) guess enough of the key to decrypt up one round, checking whether the low-order bit of the difference is as expected.
Previous | Table of Contents | Next |